#include <stdlib.h>
#include <stdio.h>
#include <ctype.h>
#include <string.h>

#include "imbus_internal.h"
#include "im_list.h"

#define _im_list_alloc()             im_slice_new (IMList)
#define _im_list_alloc0()            im_slice_new0 (IMList)
#define _im_list_free_node(list)     im_slice_delete (IMList, list)

/****************************** Public functions **************************/
IMList *
im_list_alloc (void)
{
    return _im_list_alloc0 ();
}

void
im_list_free (IMList *list)
{
    IMList *next;

    if (list->prev)
        list->prev->next = 0;

    while (list) {
        next = list->next;
        _im_list_free_node (list);
        list = next;
    }
}

void
im_list_free_node (IMList *list)
{
    _im_list_free_node (list);
}

IMList *
im_list_append (IMList *list, IMPointer data)
{
    IMList *new_list;
    IMList *last;

    new_list = _im_list_alloc ();
    new_list->data = data;
    new_list->next = 0;

    if (list) {
        last = im_list_last (list);
        /* _im_assert (last != 0); */
        last->next = new_list;
        new_list->prev = last;

        return list;
    } else {
        new_list->prev = 0;
        return new_list;
    }
}

IMList *
im_list_prepend (IMList *list, IMPointer data)
{
    IMList *new_list;

    new_list = _im_list_alloc ();
    new_list->data = data;
    new_list->next = list;

    if (list) {
        new_list->prev = list->prev;
        if (list->prev)
            list->prev->next = new_list;
        list->prev = new_list;
    } else {
        new_list->prev = 0;
    }

    return new_list;
}

IMList *
im_list_insert (IMList *list, IMPointer data, IMInt position)
{
    IMList *new_list;
    IMList *tmp_list;

    if (position < 0)
        return im_list_append (list, data);
    else if (position == 0)
        return im_list_prepend (list, data);

    tmp_list = im_list_nth (list, position);
    if (!tmp_list)
        return im_list_append (list, data);

    new_list = _im_list_alloc ();
    new_list->data = data;
    new_list->prev = tmp_list->prev;
    if (tmp_list->prev)
        tmp_list->prev->next = new_list;
    new_list->next = tmp_list;
    tmp_list->prev = new_list;

    if (tmp_list == list)
        return new_list;
    else
        return list;
}

IMList *
im_list_insert_before (IMList *list, IMList *sibling, IMPointer data)
{
    if (!list) {
        list = im_list_alloc ();
        list->data = data;
        _im_return_val_if_fail (sibling == 0, list);
        return list;
    } else if (sibling) {
        IMList *node;

        node = _im_list_alloc ();
        node->data = data;
        node->prev = sibling->prev;
        node->next = sibling;
        sibling->prev = node;
        if (node->prev) {
            node->prev->next = node;
            return list;
        } else {
            _im_return_val_if_fail (sibling == list, node);
            return node;
        }
    } else {
        IMList *last;

        last = list;
        while (last->next)
            last = last->next;

        last->next = _im_list_alloc ();
        last->next->data = data;
        last->next->prev = last;
        last->next->next = NULL;

        return list;
    }
}

IMList *
im_list_concat (IMList *list1, IMList *list2)
{
    IMList *tmp_list;

    if (list2) {
        tmp_list = im_list_last (list1);
        if (tmp_list)
            tmp_list->next = list2;
        else
            list1 = list2;
        list2->prev = tmp_list;
    }

    return list1;
}

IMList *
im_list_remove (IMList *list, IMConstPointer data)
{
    IMList *tmp;

    tmp = list;
    while (tmp) {
        if (tmp->data != data)
            tmp = tmp->next;
        else {
            if (tmp->prev)
                tmp->prev->next = tmp->next;
            if (tmp->next)
                tmp->next->prev = tmp->prev;

            if (list == tmp)
                list = list->next;

            _im_list_free_node (tmp);

            break;
        }
    }
    return list;
}

IMList *
im_list_remove_all (IMList *list, IMConstPointer data)
{
    IMList *tmp = list;

    while (tmp) {
        if (tmp->data != data)
            tmp = tmp->next;
        else {
            IMList *next = tmp->next;

            if (tmp->prev)
                tmp->prev->next = next;
            else
                list = next;
            if (next)
                next->prev = tmp->prev;

            _im_list_free_node (tmp);
            tmp = next;
        }
    }
    return list;
}

static inline IMList *
_im_list_remove_link (IMList *list, IMList *link)
{
    if (link) {
        if (link->prev)
            link->prev->next = link->next;
        if (link->next)
            link->next->prev = link->prev;

        if (link == list)
            list = list->next;

        link->next = 0;
        link->prev = 0;
    }

    return list;
}

IMList *
im_list_remove_link (IMList *list, IMList *link)
{
    return _im_list_remove_link (list, link);
}

IMList *
im_list_delete_link (IMList *list, IMList *link)
{
    list = _im_list_remove_link (list, link);
    _im_list_free_node (link);

    return list;
}

IMList *
im_list_clone (IMList *list)
{
    IMList *new_list = 0;

    if (list) {
        IMList *last;

        new_list = _im_list_alloc ();
        new_list->data = list->data;
        new_list->prev = 0;
        last = new_list;
        list = list->next;
        while (list) {
            last->next = _im_list_alloc ();
            last->next->prev = last;
            last = last->next;
            last->data = list->data;
            list = list->next;
        }
        last->next = 0;
    }

    return new_list;
}

IMList *
im_list_reverse (IMList *list)
{
    IMList *last;

    last = 0;
    while (list) {
        last = list;
        list = last->next;
        last->next = last->prev;
        last->prev = list;
    }

    return last;
}

IMList *
im_list_nth (IMList *list, IMUInt n)
{
    while ((n-- > 0) && list)
        list = list->next;

    return list;
}

IMList *
im_list_nth_prev (IMList *list, IMUInt n)
{
    while ((n-- > 0) && list)
        list = list->prev;

    return list;
}

IMPointer
im_list_nth_data (IMList *list, IMUInt n)
{
    while ((n-- > 0) && list)
        list = list->next;

    return list ? list->data : 0;
}

IMList *
im_list_find (IMList *list, IMConstPointer data)
{
    while (list) {
        if (list->data == data)
            break;
        list = list->next;
    }

    return list;
}

IMList *
im_list_find_custom (IMList *list, IMConstPointer data, IMCompareFunc func)
{
    _im_return_val_if_fail (func != 0, list);

    while (list) {
        if (!func (list->data, data))
            return list;
        list = list->next;
    }

    return 0;
}


IMInt
im_list_position (IMList *list, IMList *link)
{
    IMInt i;

    i = 0;
    while (list) {
        if (list == link)
            return i;
        i++;
        list = list->next;
    }

    return -1;
}

IMInt
im_list_index (IMList *list, IMConstPointer data)
{
    IMInt i;

    i = 0;
    while (list) {
        if (list->data == data)
            return i;
        i++;
        list = list->next;
    }

    return -1;
}

IMList *
im_list_last (IMList *list)
{
    if (list) {
        while (list->next)
            list = list->next;
    }

    return list;
}

IMList *
im_list_first (IMList *list)
{
    if (list) {
        while (list->prev)
            list = list->prev;
    }

    return list;
}

IMUInt
im_list_length (IMList *list)
{
    IMUInt length;

    length = 0;
    while (list) {
        length++;
        list = list->next;
    }

    return length;
}

void
im_list_foreach (IMList *list, IMFunc func, IMPointer user_data)
{
    while (list) {
        IMList *next = list->next;
        (*func) (list->data, user_data);
        list = next;
    }
}

static IMList *
im_list_insert_sorted_real (IMList *list,
                            IMPointer data, IMFunc func, IMPointer user_data)
{
    IMList *tmp_list = list;
    IMList *new_list;
    IMInt cmp;

    _im_return_val_if_fail (func != 0, list);

    if (!list) {
        new_list = _im_list_alloc0 ();
        new_list->data = data;
        return new_list;
    }

    cmp = ((IMCompareDataFunc) func) (data, tmp_list->data, user_data);

    while ((tmp_list->next) && (cmp > 0)) {
        tmp_list = tmp_list->next;

        cmp = ((IMCompareDataFunc) func) (data, tmp_list->data, user_data);
    }

    new_list = _im_list_alloc0 ();
    new_list->data = data;

    if ((!tmp_list->next) && (cmp > 0)) {
        tmp_list->next = new_list;
        new_list->prev = tmp_list;
        return list;
    }

    if (tmp_list->prev) {
        tmp_list->prev->next = new_list;
        new_list->prev = tmp_list->prev;
    }
    new_list->next = tmp_list;
    tmp_list->prev = new_list;

    if (tmp_list == list)
        return new_list;
    else
        return list;
}

IMList *
im_list_insert_sorted (IMList *list, IMPointer data, IMCompareFunc func)
{
    return im_list_insert_sorted_real (list, data, (IMFunc) func, 0);
}

IMList *
im_list_insert_sorted_with_data (IMList *list,
                                 IMPointer data,
                                 IMCompareDataFunc func,
                                 IMPointer user_data)
{
    return im_list_insert_sorted_real (list, data, (IMFunc) func, user_data);
}

static IMList *
im_list_sort_merge (IMList *l1,
                    IMList *l2, IMFunc compare_func, IMPointer user_data)
{
    IMList list, *l, *lprev;
    IMInt cmp;

    l = &list;
    lprev = 0;

    while (l1 && l2) {
        cmp =
            ((IMCompareDataFunc) compare_func) (l1->data, l2->data,
                                                user_data);

        if (cmp <= 0) {
            l->next = l1;
            l1 = l1->next;
        } else {
            l->next = l2;
            l2 = l2->next;
        }
        l = l->next;
        l->prev = lprev;
        lprev = l;
    }
    l->next = l1 ? l1 : l2;
    l->next->prev = l;

    return list.next;
}

static IMList *
im_list_sort_real (IMList *list, IMFunc compare_func, IMPointer user_data)
{
    IMList *l1, *l2;

    if (!list)
        return 0;
    if (!list->next)
        return list;

    l1 = list;
    l2 = list->next;

    while ((l2 = l2->next) != 0) {
        if ((l2 = l2->next) == 0)
            break;
        l1 = l1->next;
    }
    l2 = l1->next;
    l1->next = 0;

    return
        im_list_sort_merge (im_list_sort_real (list, compare_func, user_data),
                            im_list_sort_real (l2, compare_func, user_data),
                            compare_func, user_data);
}

IMList *
im_list_sort (IMList *list, IMCompareFunc compare_func)
{
    return im_list_sort_real (list, (IMFunc) compare_func, 0);
}

IMList *
im_list_sort_with_data (IMList *list,
                        IMCompareDataFunc compare_func, IMPointer user_data)
{
    return im_list_sort_real (list, (IMFunc) compare_func, user_data);
}


/*
vi:ts=4:nowrap:ai:expandtab
*/
